1581. Игра с кубиком

У Джона есть стандартный игральный кубик с 6 гранями, пронумерованных от 1 до 6. Каждый раз после его бросания Джон получает от мамы столько конфет, сколько выпадет косточек на верхней грани. Мальчик хочет узнать, сколько раз ему необходимо бросать кубик, чтобы суммарно получить от мамы не менее candies конфет.

Вход. Каждая строка содержит одно число – желаемое количество конфет candies (1 ≤ candies ≤ 10⁶).

Выход. Для каждого значения candies в отдельной строке вывести ожидаемое количество бросков кубика. Каждое число следует выводить с 4 цифрами после десятичной точки.

Пример входа

1

2

7

47

Пример выхода

1.0000

1.1667

2.5216

13.9048

РЕШЕНИЕ

вероятность - динамическое программированике

Анализ алгоритма

Пусть r[i] содержит количество бросков, необходимое для получения в точности i конфет. Очевидно, что r[0] = 0, а также r[i] = 0 при i < 0.

Для i > 0 имеем соотношение:

На кубике может выпасть число от 1 до 6. Для получения в точности i конфет можно, например, получить i – k (1 ≤ k ≤ 6) конфет, после чего бросить кубик и с вероятностью 1 / 6 получить еще k конфет.

Последовательно вычисляем значения r[i] для i от 1 до candies и возвращаем r[candies].

Реализация алгоритма

Объявим глобальный массив r.

double r[1000001];

Функция expectedThrows вычисляет элементы массива r[i] согласно выше приведенной формуле.

double expectedThrows(int candies)

{

int i, j;

double s;

r[0] = 0;

for(i = 1; i <= candies; i++)

{

for(s = 0, j = max(i-6,0); j < i; j++)

s += r[j];

r[i] = 1 + s / 6;

}

return r[candies];

}

Основная часть программы.

while(scanf("%d",&n) == 1)

{

res = expectedThrows(n);

printf("%.4lf\n",res);

}